Minimizing a Submodular Function on a Lattice
Topkis, D. M. (1978). Minimizing a submodular function on a lattice. Operations research, 26(2), 305-321. PDF claude.iconこの論文は、以下の内容を含む、サブモジュラー関数の最小化問題に関する理論的な研究です。
1. パラメータに依存する目的関数と制約条件を持つ最適化問題の集合において、最適解がパラメータの単調増加関数になるための一般的な条件を与えている。 3. 格子の空でない部分格子の集合に自然な半順序関係を導入し、その性質を示している。 4. サブモジュラー性と反トーン差分の関係を明らかにし、サブモジュラー関数を生成・保存する操作を示している。 5. サブモジュラー関数を最小化する問題で、最適解集合が部分格子になること、最大・最小元を持つための条件を与えている。
6. 格子の部分格子上で定義されたサブモジュラー関数を、全体の格子上のサブモジュラー関数に拡張できる条件を示している。
7. 最適解集合がパラメータに関して単調増加になること、単調増加な最適解が存在することの十分条件を導出している。
8. サブモジュラー関数と凸関数の類似点にも言及している。 様々な分野への応用可能性が指摘されており、ネットワークフロー、ゲーム理論、在庫理論、数理計画法などへの適用例が後続の論文で示されている、理論的にも応用的にも重要な内容を含んだ論文と言えます。